package BinaryTree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class InorderTraversal94 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        root.right = node1;
        node1.left = node2;
        for (Integer integer : new InorderTraversal94().inorderTraversal1(root)) {
            System.out.println(integer);
        }
    }

    public List<Integer> inorderTraversal1(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        ArrayDeque<TreeNode> stack = new ArrayDeque<>();

        if(root == null){
            return list;
        }else if(root.left == null && root.right == null){
            list.add(root.val);
            return list;
        }

        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.pop();
                list.add(root.val);
                root= root.right;
            }
        }

        return list;
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inoreder(root,list);
        return list;
    }

    public void inoreder(TreeNode root, ArrayList<Integer> list) {
        if(root == null){
            return;
        }
        inoreder(root.left,list);
        list.add(root.val);
        inoreder(root.right,list);
    }
}
